// @before-stub-for-debug-begin
#include <vector>
#include <string>
#include <algorithm>
#include <numeric>
#include "commoncppproblem888.h"

using namespace std;
// @before-stub-for-debug-end

/*
 * @FilePath: \undefinedc:\Users\sxjct\.leetcode\888.公平的糖果棒交换.cpp
 * @Brief: 
 * @Version: 1.0
 * @Date: 2021-03-19 10:36:14
 * @Author: tianyiyi
 * @Copyright: Copyright@tianyiyi
 * @LastEditors: Mr.Tian
 * @LastEditTime: 2021-03-19 10:53:41
 */
/*
 * @lc app=leetcode.cn id=888 lang=cpp
 *
 * [888] 公平的糖果棒交换
 */

// @lc code=start
class Solution {
public:
    vector<int> fairCandySwap(vector<int>& A, vector<int>& B) {
        int sumA = accumulate(A.begin(),A.end(),0);
        int sumB = accumulate(B.begin(),B.end(),0);

        int temp = (sumA - sumB) / 2;

        sort(A.begin(),A.end());
        sort(B.begin(),B.end());

        int i = 0;
        int j = 0;
        int nA = A.size();
        int nB = B.size();
        while(i < nA && j < nB)
        {
            int curr = A[i] - B[j];
            if(curr == temp)
            {
                return {A[i],B[j]};
            }
            else if(curr < temp)
            {
                i++;
            }
            else
            {
                j++;
            }
        }
        return vector<int>();
    }
};
// @lc code=end

